package com.sunny.l42;

import java.util.ArrayList;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(null == root)
            return res;
        Stack<ArrayList<Integer>> stack = new Stack<>();
        LinkedBlockingQueue<TreeNode> queue1 = new LinkedBlockingQueue<>();
        LinkedBlockingQueue<TreeNode> queue2 = new LinkedBlockingQueue<>();
        int size1 = 1;
        int size2 = 0;
        int tag = 1;
        queue1.offer(root);
        ArrayList<Integer> arrayList = new ArrayList<>();
        while ((1 == tag && !queue1.isEmpty()) || (2 == tag && !queue2.isEmpty())){
            if(1 == tag){
                TreeNode node = queue1.poll();
                arrayList.add(node.val);
                size1--;
                if(null != node.left){
                    queue2.offer(node.left);
                    size2++;
                }
                if(null != node.right){
                    queue2.offer(node.right);
                    size2++;
                }
                if(0 == size1){
                    stack.push(arrayList);
                    tag = 2;
                    arrayList = new ArrayList<>();
                }
            }else if(2 == tag){
                TreeNode node = queue2.poll();
                arrayList.add(node.val);
                size2--;
                if(null != node.left){
                    queue1.offer(node.left);
                    size1++;
                }
                if(null != node.right){
                    queue1.offer(node.right);
                    size1++;
                }
                if(0 == size2){
                    stack.push(arrayList);
                    tag = 1;
                    arrayList = new ArrayList<>();
                }
            }
        }

        while (!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
